The present invention relates to multicasting in a communications network and, more particularly, to a method and apparatus for port memory multicast cell tracking in common memory switches for use in an asynchronous transfer mode (ATM) network.
ATM networks pass data in the form of cells. The cells, which are of fixed size, pass through one or more switches on the way to a specified destination that may be another switch, a terminal, or some other component in the network. An individual cell may need to be sent to several different destinations in the network from a single switch.
For purposes of this discussion, the term "multicasting" refers to the distribution of a cell to multiple destinations. When multicasting, an individual cell is copied in a switch, and the copies are sent to multiple destinations from the switch. In a common memory switch, the cell copying operation can be efficiently achieved by storing the cell in memory and generating multiple copies of the cell memory location (the cell address). Each copy of the cell address is stored at an output queue of the switch. A count memory stores a count of the number of copies of the cell made and transmitted. As copies of the cell exit the switch, the count in the count memory decrements. When the last cell copy is transmitted, the value of the count in the count memory is zero. At this point the address can be reused for another cell and is returned to a list of free memory locations.
One known multicast cell counting implementation uses a single memory to count the cell copies exiting the switch. FIG. 1 is useful for discussing the single memory multicast count implementation. This implementation requires several memory operations to track cell copies. The cell count value (ie., the number of copies of the cell to be transmitted) is written to the memory 10 on enqueue, i.e., when a cell enters the switch (step 12). When a cell leaves the switch, the cell count value is read (step 14) from the multicast count memory and decremented (step 16). The decremented count value is then written to and stored in the multicast count memory (step 18). A cell count value of zero indicates all cell copies have been transmitted from the switch to the intended destinations.
This approach thus requires three memory accesses on the memory per cell cycle. For purposes of this discussion, a cell "cycle" is the enqueuing of a single cell to a switch and the dequeuing of that cell from the switch. Since three memory accesses are performed for each cell cycle, the memory must function three times as fast as the cell rate. This performance requirement for the memory greatly limits the types of memory that can successfully perform the task of multicast counting in high capacity common memory switches. Generally, only small, fast memories are capable of supporting this implementation. This limits the capacity of the switch or restricts the number of memory locations that can be used for multicast cells, as the multicast counting operation is the most demanding (in terms of memory bandwidth) in a common memory switch.
Another known cell counting implementation is disclosed and claimed in U.S. patent application Ser. No. 08/994,792, titled "Method and Apparatus for Banked Multicast Common Memory Switches" and filed on Dec. 19, 1997, which is hereby expressly incorporated by reference. In this implementation, two separate memories are used to count cell copies to be transmitted, resulting in a reduced number of memory accesses per memory per cycle. While this approach is an improvement over the single memory implementation, it can not dequeue cells at the full rate when commercial L2 cache memory and banking techniques are used.
It is, therefore, desirable to provide a method and apparatus for multicasting incorporating a cell tracking strategy having a reduced number of per-memory accesses and capable of cell dequeue rates that permit use of commercial memories.